package likou.jindian;

import java.util.Arrays;
import java.util.Comparator;

/**
 * @author: 唐小尊
 * @email: 1171702529@qq.com
 * @cate: 2021/05/18 09:14
 */
public class _16_16 {
    public int[] subSort(int[] array) {
        int[][] nums = new int[array.length][2];
        for (int i = 0; i < array.length; i++) {
            nums[i][0] = array[i];
            nums[i][1] = i;
        }
        Arrays.sort(nums, new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                return o1[0]-o2[0];
            }
        });
        int start = 0,end =0;
        for (int i=0;i<nums.length;i++){
            if (nums[i][1]!=i){
                start = i;
                break;
            }
        }
        for (int i=nums.length-1;i>0;i--){
            if (nums[i][1]!=i){
                end = i;
                break;
            }
        }
        return new int[]{start,end};
    }

    /**
     * 最优解
     * @param array
     * @return
     */
    public int[] subSort2(int[] array) {
        int N = array.length, start = -1, end = -1;
        int min = Integer.MAX_VALUE, max = Integer.MIN_VALUE;

        // 从前往后找目标末位，使得从该位到最后，数组保持递增
        for (int i = 0; i < N; i++) {
            if (array[i] >= max) max = array[i];
            else end = i;
        }

        // 数组恒递增，说明数组是有序的，直接返回
        if (end == -1) return new int[] {-1, -1};

        // 从后往前找目标首位，使得从该位到最前，数组保持递减
        for (int i = end; i >= 0; i--) {
            if (array[i] <= min) min = array[i];
            else start = i;
        }
        return new int[] {start, end};
    }
}
